package Atop100.huisu;

import java.util.ArrayList;
import java.util.List;

public class Class39 {

//        public List<String> generateParenthesis(int n) {
//            List<String> ans = new ArrayList<String>();
//            backtrack(ans, new StringBuilder(), 0, 0, n);
//            return ans;
//        }
//
//
//        public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
//            if (cur.length() == max * 2) {
//                ans.add(cur.toString());
//                return;
//            }
//            if (open < max) {
//                cur.append('(');
//                backtrack(ans, cur, open + 1, close, max);
//                cur.deleteCharAt(cur.length() - 1);
//            }
//            if (close < open) {
//                cur.append(')');
//                backtrack(ans, cur, open, close + 1, max);
//                cur.deleteCharAt(cur.length() - 1);
//            }
//        }
//
//
//    class Solution {
//
//        public List<String> generateParenthesis(int n) {
//            List<String> combinations = new ArrayList<String>();
//            generateAll(new char[2 * n], 0, combinations);
//            return combinations;
//        }
//
//        public void generateAll(char[] current, int pos, List<String> result) {
//            if (pos == current.length) {
//                if (valid(current)) {
//                    result.add(new String(current));
//                }
//            } else {
//                current[pos] = '(';
//                generateAll(current, pos + 1, result);
//                current[pos] = ')';
//                generateAll(current, pos + 1, result);
//            }
//        }
//
//
//        public boolean valid(char[] current) {
//            int balance = 0;
//            for (char c: current) {
//                if (c == '(') {
//                    ++balance;
//                } else {
//                    --balance;
//                }
//                if (balance < 0) {
//                    return false;
//                }
//            }
//            return balance == 0;
//        }
//
//    }

        List<String> res = new ArrayList<>();
        public List<String> generateParenthesis(int n) {
            if(n <= 0){
                return res;
            }
            getParenthesis("",n,n);
            return res;
        }

        private void getParenthesis(String str,int left, int right) {
            if(left == 0 && right == 0 ){
                res.add(str);
                return;
            }
            if(left == right){
                //剩余左右括号数相等，下一个只能用左括号
                getParenthesis(str+"(",left-1,right);
            }else if(left < right){
                //剩余左括号小于右括号，下一个可以用左括号也可以用右括号
                if(left > 0){
                    getParenthesis(str+"(",left-1,right);
                }
                getParenthesis(str+")",left,right-1);
            }
        }


    public static void main(String[] args) {
        Class39 class39 = new Class39();
        List<String> strings = class39.generateParenthesis(3);
        System.out.println(strings.toString());

    }



}
